class Solution {
public:
    int cherryPickup(std::vector<std::vector<int>>& g) {
        int n = g.size();      // 获取矩阵的行数
        int m = g[0].size();   // 获取矩阵的列数
        
        // 初始化缓存数组 cache，用于记忆化搜索
        // cache[i][j][k] 表示机器人A在第i行、第j列位置，机器人B在第i行、第k列位置时，能采集的最大樱桃数
        vector<vector<vector<int>>> cache(
            n, vector<vector<int>>(m, vector<int>(m, -1))
        );

        // 定义递归函数 dfs 来计算从当前状态 (i, j, k) 开始，两个机器人能采集到的最大樱桃数
        auto dfs = [&](auto&& self, int i, int j, int k) -> int {
            // 边界条件：如果任何一个机器人越界，返回0，因为不能继续采集樱桃
            if (i < 0 || i >= n || j < 0 || j >= m || k < 0 || k >= m)
                return 0;

            // 如果当前状态已经计算过，直接返回缓存中的结果
            if (cache[i][j][k] != -1)
                return cache[i][j][k];

            int ans = 0;
            // 计算当前格子可以采集的樱桃数
            // 如果机器人A和B处在同一个格子（即 j == k），只算一次樱桃
            int val = (j == k) ? g[i][j] : g[i][j] + g[i][k];

            // 尝试所有九种可能的移动组合，分别为：
            // 1. 机器人A向下走、机器人B向下走
            // 2. 机器人A向下走、机器人B向下左走
            // 3. 机器人A向下走、机器人B向下右走
            // 4. 机器人A向下左走、机器人B向下走
            // 5. 机器人A向下左走、机器人B向下左走
            // 6. 机器人A向下左走、机器人B向下右走
            // 7. 机器人A向下右走、机器人B向下走
            // 8. 机器人A向下右走、机器人B向下左走
            // 9. 机器人A向下右走、机器人B向下右走

            // 递归计算每种情况，并取最大的值
            ans = std::max(ans, val + self(self, i + 1, j, k));          // A 下走，B 下走
            ans = std::max(ans, val + self(self, i + 1, j + 1, k));      // A 下走，B 下左走
            ans = std::max(ans, val + self(self, i + 1, j - 1, k));      // A 下走，B 下右走
            ans = std::max(ans, val + self(self, i + 1, j, k + 1));      // A 下走，B 下右走
            ans = std::max(ans, val + self(self, i + 1, j, k - 1));      // A 下走，B 下左走
            ans = std::max(ans, val + self(self, i + 1, j + 1, k + 1));  // A 下左走，B 下右走
            ans = std::max(ans, val + self(self, i + 1, j - 1, k - 1));  // A 下右走，B 下左走
            ans = std::max(ans, val + self(self, i + 1, j + 1, k - 1));  // A 下左走，B 下右走
            ans = std::max(ans, val + self(self, i + 1, j - 1, k + 1));  // A 下右走，B 下左走

            // 将当前状态的最大樱桃数存入 cache，以便下次使用
            cache[i][j][k] = ans;

            // 返回当前状态的最大樱桃数
            return ans;
        };

        // 从初始位置 (0, 0) 和 (0, m-1) 开始计算最大樱桃数
        return dfs(dfs, 0, 0, m - 1);
    }
};
